package 图论述

/*
https://leetcode.cn/problems/number-of-islands/?envType=study-plan-v2&envId=top-100-liked

200. 岛屿数量
给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。

示例 1：
输入：grid = [

	["1","1","1","1","0"],
	["1","1","0","1","0"],
	["1","1","0","0","0"],
	["0","0","0","0","0"]

]
输出：1

示例 2：
输入：grid = [

	["1","1","0","0","0"],
	["1","1","0","0","0"],
	["0","0","1","0","0"],
	["0","0","0","1","1"]

]
输出：3

思路: 使用深度优先搜索
将二维网格看成一个无向图, 竖直或者水平相邻的1之间有边
*/
func numIslands(grid [][]byte) int {
	nums := 0                        //1.声明结果计
	for i := 0; i < len(grid); i++ { //2.遍历二维网格的每个单元格,进行深度搜索
		for j := 0; j < len(grid[0]); j++ {

			//如果当前单元格为'1',进行深度搜索,将与本次单元格连接成岛屿的单元格,都转化为0
			//然后岛屿计数+1
			if grid[i][j] == '1' {
				DFS(&grid, i, j)
				nums++
			}
		}
	}
	return nums
}
func DFS(grid *[][]byte, i int, j int) {
	row := len(*grid) //获取二维数组长度,宽度
	col := len((*grid)[0])
	//如果i,j超过边界范围了, 直接返回
	if i < 0 || i >= row || j < 0 || j >= col {
		return
	}
	//深度搜索,将与本次单元格连接成岛屿的单元格,都转化为0  这样是为了消除构成当前岛屿的单元格, 避免对后续岛屿数量统计产生影响
	if (*grid)[i][j] == '1' {
		(*grid)[i][j] = '0'
		DFS(grid, i-1, j)
		DFS(grid, i+1, j)
		DFS(grid, i, j-1)
		DFS(grid, i, j+1)
	}
}
